/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 马拉圈
 * Date: 2023-06-13
 * Time: 23:30
 */
public class Main {
    public int tribonacci(int n) {
        //1. 创建dp表
        int[] src = new int[3];
        src[0] = 0;
        src[1] = 1;
        src[2] = 1;

        //2. 初始化
        if(n == 0) {
            return 0;
        }
        if(n == 1 || n == 2) {
            return 1;
        }

        int ret = 0;
        //3. 填表
        for(int i = 3; i < n + 1; i++) {
            ret = src[0] + src[1] + src[2];
            src[0] = src[1];
            src[1] = src[2];
            src[2] = ret;
        }
        //4. 返回值
        return ret;
    }
    public int waysToStep(int n) {
        //1. 创建表
        int[] dp = new int[n + 1];
        int DOM = (int)1e9 + 7; //取模数

        //2. 初始化
        if(n == 1) {
            return 1;
        }
        if(n == 2) {
            return 2;
        }
        if(n == 3) {
            return 4;
        }
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        //3. 填表
        for(int i = 4; i < n + 1; i++) {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % DOM + dp[i - 3]) % DOM;
        }

        //4. 返回值
        return dp[n];
    }
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        //1. 创建dp表
        int[] dp = new int[n + 1];
        //2. 初始化，处理边界
        if(n == 0 || n == 1) {
            return 0;
        }
        dp[n] = 0;
        dp[n - 1] = cost[n - 1];
        //3. 填表
        for(int i = n - 2; i >= 0; i--) {
            dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];
        }
        //4. 返回值
        return Math.min(dp[0], dp[1]);
    }
    public int numDecodings(String s) {
        int n = s.length();

        char[] string = s.toCharArray();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        if(string[0] != '0') {
            dp[1] += 1;
        }
        if(n == 1) {
            return dp[1];
        }
        for(int i = 2; i < n + 1; i++) {
            if(string[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            int number = (string[i - 2] - '0') * 10 + string[i - 1] - '0';
            if(number >= 10 && number <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }




}
